// 1. 我们希望下一个数比当前数字大，这样才能满足下一个排列的定义，因此只需要将后面的大数与前面的小数
// 交换，就能得到更大的一个数
// 2. 我们还希望下一个数增加的幅度尽可能的小，这样才能满足 下一个排列与当前排列紧邻 的要求，为了满足
// 这个要求，我们需要：
// 1. 在尽可能靠右的低位进行交换，需要从后向前查找
// 2. 将一个尽可能小的大数与前面的小数进行交换，比如 123465，下一个排列应该把 5 和 4 交换，而不是 6
// 和 4 交换
// 3. 将大数换到前面后，需要将大数后面的数重置为升序，升序排列就是最小的排列，以 123465 为例
// 首先按照第一步，交换 5 和 4，得到 123564
// 然后需要将 5 之后的数重置为升序，得到 123546，显然 123546 比 123564 更小，123546 就是 123465 的
// 下一个排列

var nextPermutation = function (nums) {
  if (nums.length <= 1) return;
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i >= 0) {
    let j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
      j--;
    }
    swap(nums, i, j);
  }
  reverse(nums, i + 1);
};

function reverse(nums, start) {
  let i = start,
    j = nums.length - 1;
  while (i < j) {
    swap(nums, i, j);
    i++;
    j--;
  }
}

function swap(nums, i, j) {
  let temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
